package com.yuan.algorithms.arithmetic_2;
/*
 * 二叉查找树的实现
 */

class TreeNode {
	private Object data;//数据域
	private TreeNode parent;//父节点
	private TreeNode lChild;//左孩子
	private TreeNode rChild;//右孩子
	private int height;//以该结点为根的子树的高度
	private int size;//该结点子孙数（包括节点本身）
	private int index;//二叉查找树数据的下标
	public TreeNode() {
		this(null, -1);
	}
	public TreeNode(Object e, int i) {
		data = e;
		height = 0;
		size = 1;
		parent = lChild = rChild = null;
		index = i;
	}
	
	/**
	 * 获取数据
	 * @return
	 */
	public Object getData() {
		return data;
	}
	
	/**
	 * 设置数据
	 * @param data
	 */
	public void setData(Object data) {
		this.data = data;
	}
	
	/****判断当前结点的位置情况****/
	/**
	 * 判断是否有父亲
	 * @return
	 */
	public boolean hasParent() {
		return parent != null;
	}
	
	/**
	 * 判断是否有左孩子
	 * @return
	 */
	public boolean hasLChild() {
		return lChild != null;		
	}
	
	/**
	 * 判断是否有右孩子
	 * @return
	 */
	public boolean hasRChild() {
		return rChild != null;		
	}
	
	/**
	 * 判断是否是叶子结点
	 * @return
	 */
	public boolean isLeaf() {
		return !hasLChild() && !hasRChild();
	}
	
	/**
	 * 判断是否是某结点的左孩子
	 * @return
	 */
	public boolean isLChild() {
		return (hasLChild() && this==parent.getLChild());
	}
	
	/**
	 * 判断是否是某结点的右孩子
	 * @return
	 */
	public boolean isRChild() {
		return (hasRChild() && this==parent.rChild);
	}
	
	/****与height有关的方法****/
	
	/**
	 * 取结点的高度，即以该结点为根的树的高度
	 * @return
	 */
	public int getHeight() {
		return height;
	}
	
	/**
	 * 更新当前结点及其祖先的高度
	 */
	public void updateHeight() {
		int newH = 0;//新高度初始化为0，高度等于左右子树高度加1中的大者
		if (hasLChild()) {
			newH = Math.max(newH, 1 + getLChild().getHeight());
		}
		if (hasRChild()) {
			newH = Math.max(newH, 1 + getRChild().getHeight());
		}
		if (newH==height) {
			//高度没有发生变化则直接返回
			return;
		}
		height = newH;
		if (hasParent()) {
			//递归更新祖先的高度
			getParent().updateHeight();
		}
	}
	
	/****与parent相关的方法****/
	
	/**
	 * 取父结点
	 * @return
	 */
	public TreeNode getParent() {
		return parent;
	}
	
	/**
	 * 断开与父亲的关系
	 */
	public void sever() {
		if (!hasParent()) {
			return;
		}
		if (isLChild()) {
			parent.lChild = null;
		}else {
			parent.rChild = null;
		}
		parent.updateHeight();
		parent.updateSize();
		parent = null;
	}
	
	/****与Child有关的方法****/
	
	/**
	 * 取左孩子
	 * @return
	 */
	public TreeNode getLChild() {
		return lChild;
	}
	
	/**
	 * 取右孩子
	 * @return
	 */
	public TreeNode getRChild() {
		return rChild;
	}
	
	/**
	 * 设置当前结点的左孩子，返回原左孩子
	 * @param lc
	 * @return
	 */
	public TreeNode setLChild(TreeNode lc) {
		TreeNode oldLC = this.lChild;
		if (hasLChild()) {
			lChild.sever();//断开当前左孩子与结点的关系
		}
		if (lc != null) {
			lc.sever();//断开lc与其父节点的关系
			this.lChild = lc;//确立父子关系
			lc.parent = this;
			this.updateHeight();//更新当前节点及其祖先高度
			this.updateSize();//更新当前节点及其祖先规模
		}
		return oldLC;
	}
	
	/**
	 * 设置当前结点的右孩子，返回原右孩子
	 * @param rc
	 * @return
	 */
	public TreeNode setRChild(TreeNode rc) {
		TreeNode oldRC = this.rChild;
		if (hasRChild()) {
			rChild.sever();//断开当前右孩子与结点的关系
		}
		if (rc != null) {
			rc.sever();//断开rc与其父节点的关系
			this.rChild = rc;//确立父子关系
			rc.parent = this;
			this.updateHeight();//更新当前节点及其祖先高度
			this.updateSize();//更新当前节点及其祖先规模
		}
		return oldRC;
	}
	
	/****与size有关的方法****/
	
	/**
	 * 取以该结点为根的树的结点数
	 * @return
	 */
	public int getSize() {
		return size;
	}
	
	/**
	 * 更新当前结点及其祖先的子孙数
	 */
	public void updateSize() {
		size = 1;//初始化为1（结点本身）
		if (hasLChild()) {
			size += getLChild().getSize();//加上左子树规模
		}
		if (hasRChild()) {
			size += getRChild().getSize();//加上右子树规模
		}
		if (hasParent()) {
			getParent().updateHeight();//递归更新祖先的规模
		}
	}
	
	/**
	 * 在二叉查找树中插入新元素
	 * @param root 树的根节点
	 * @param e 插入的元素
	 * @param i 元素的下标
	 */
	public void insert(TreeNode root, double e, int i) {
		if ((double)root.getData() >= e) {
			if (root.getLChild()==null)
				root.setLChild(new TreeNode(e, i));
			else {
				root = root.getLChild();
				insert(root, e, i);
			}
		}else {
			if (root.getRChild()==null) {
				root.setRChild(new TreeNode(e, i));
			}else {
				root = root.getRChild();
				insert(root, e, i);
			}
		}
	}

	/**
	 * 返回树中元素的最大值
	 * @return
	 */
	public double max() {
		TreeNode root = this;
		double rs = (double) root.getData();
		while(root.hasRChild()) {
			root = root.getRChild();
			rs = (double) root.getData();
		}
		return rs;
	}

	/**
	 * 返回树中元素的最小值
	 * @return
	 */
	public double min() {
		TreeNode root = this;
		double rs = (double) root.getData();
		while(root.hasLChild()) {
			root = root.getLChild();
			rs = (double) root.getData();
		}
		return rs;
	}

	/**
	 * 查找某个元素在树中的下标，若元素不存在则返回-1
	 * @param e
	 * @return
	 */
	public int seek(double e) {
		TreeNode root = this;
		return search(root, e);
	}
	private int search(TreeNode root, double e) {
		if (root == null) {
			return -1;
		}
		if ((double)root.getData()==e) {
			return root.index;
		}else if ((double)root.getData() > e) {
			return search(root.getLChild(), e);
		}else {
			return search(root.getRChild(), e);
		}
	}
	
	/**
	 * 删除元素i
	 * @param i
	 */
	public TreeNode remove(double i, TreeNode root) {
		if (root == null) {
			return root;
		}
		if (i > (double)root.getData()) {
			root.setRChild(remove(i, root.getRChild()));
		} else if (i < (double)root.getData()) {
			root.setLChild(remove(i, root.getLChild()));
		} else if (root.hasLChild() && root.hasRChild()) {//有两个孩子的删除
			root.setData(root.getRChild().min());//用右子树的最小值代替删除数据节点的值
			root.setRChild(remove((double) root.getData(), root.getRChild()));//递归删除该节点
		} else {
			root = root.hasLChild() ? root.getLChild() : root.getRChild();//只有一个孩子或者没有孩子，用孩子代替自己的位置
		}
		return root;
	}
}
public class BinFindTree {

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		double[] arr = {0.3, 1.632, 3.44, 5, 2.55, 1.9, 15.2, 7, 5, 8, 20, 1000, 432, 44, 87, 59, 23.34, 999};
//		double[] arr = {5,2,4,6,3};
		TreeNode tree = new TreeNode(arr[0], 0);
		for (int i = 1, len = arr.length; i < len; i++) {
			tree.insert(tree, arr[i], i);
		}
		System.out.println("Max="+tree.max());
		tree.remove(1000, tree);
		System.out.println("Max="+tree.max());
		System.out.println("Min="+tree.min());
		System.out.println(tree.seek(15.2));
		long end = System.currentTimeMillis();
		System.out.println("sumTime:"+(end-start));
	}

}
